package pfq.demo.algorithm.linkedlist;

/**
 * 链表相关的练习题：
 * 1. 链表中是否有环
 * 2. 两个有序链表的合并
 * 3. 删除链表倒数第n个结点
 * 4. 求链表的中间结点
 */
public class Practice1 {

    /**
     * 判断一个链表中是否有环
     * 思路一：
     * 遍历链表，将访问过的结点放入HashSet中，后续每访问一个结点都去这个HashSet中找下是否存在，如果存在则说明有环
     * 总结：用当前结点在所有已访问过的结点中查找
     * <p>
     * 思路二：
     * 遍历链表，每访问一个结点，就去遍历该结点之后的所有结点，如果有相同的结点则说明有环
     * 总结：用当前结点在所有未访问的结点中查找
     * <p>
     * 思路三：
     * 用两个指针同时遍历链表，一个快指针，一个慢指针，如果存在环，则两个指针一定会指向相同的结点
     * 就好比两个人同时跑操场，一个跑的快，一个跑的慢，如果不限圈数，则快的一定会追上慢的
     */
    public static boolean hasCycle(Node head) {
        if (head == null) return false;

        if (head.next == null) return false;

        Node slowNode = head;
        Node fastNode = head.next;

        while (fastNode != null && fastNode.next != null) {
            slowNode = slowNode.next;
            fastNode = fastNode.next.next;

            if (fastNode == slowNode) return true;
        }

        return false;
    }

    /**
     * 合并两个有序链表
     * 思路一：
     * 先将两个链表合并成一个，然后整体进行排序
     * <p>
     * 思路二：
     * 遍历其中一个链表，然后依次将每个结点插入到另一个链表的适当位置
     * <p>
     * 思路三：
     * 创建一个新链表，然后比较两链表的结点，较小的那个结点放到新链表中，接着指针后移继续比较，直到其中某个链表结束为止
     */
    public static void merge(Node head1, Node head2) {

    }

    /**
     * 删除链表倒数第n个结点
     * 思路一：
     * 先遍历一遍得到该链表的长度，然后减去n得到正数第几个位置，最后遍历到该位置进行删除
     * <p>
     * 思路二：
     * 两个指针，让第一个指针先指向正数第n-1个结点，第二个指针指向头结点，然后两指针同时遍历，直到第一个指针指向链尾，此时第二个指针指向的结点就是要删除的那个结点
     */
    public static void delete(Node head, int n) {

    }

    /**
     * 找到链表的中间结点
     * 思路一：
     * 先遍历一遍链表得到链表长度，然后长度/2就得到了该链表的中间结点
     * <p>
     * 思路二：
     * 使用快慢指针，慢指针每次访问一个结点，快指针每次访问两个结点，当快指针指向链尾的时候，慢指针正好指到了中间的结点
     */
    public static Node findMiddleNode(Node head) {
        return null;
    }


    public static void main(String[] args) {
        hasCycle(null);
    }

}
